package arima;

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;

import stats.ArimaStats;
import stats.MrgExpStats;

import mining.CsvReader;
import mining.ItemSetMining;
import mining.WriteStats;

public class Arima extends ItemSetMining {
	
	private static final boolean write = false; 

//	public static void main(String[] args) {
////		String location = "./datasets/connect4/connect-4.data.modified";
//		String location = "./datasets/voting_records/house-votes-84.data.modified";
//
//		System.out.println(ArimaStats.headings());
//		Arima a = new Arima(location);
//		a.setMinRareItemsetSupport(50);
//		a.setMinFreqItemsetSupport(99999999);
//		a.run();
//	}
	
	public void run() {
		if (write) {
			try
			{
				this.filename = this.filePath + "." + this.getMinRareItemsetSupport() + "." + this.getMinFreqItemsetSupport();
				this.bw = new BufferedWriter(new FileWriter(this.filename + ".arima"));
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}

		long t1 = System.nanoTime();
		
		findMinGenerators();
//		System.out.println(this.stats);

		generateRareItemsets();
		
		long t2 = System.nanoTime();
		this.aStats.runtime = (t2-t1)/1000000;

		System.out.println(this.aStats);
		WriteStats.write(this.aStats);
		if (write) {
			try
			{
				this.bw.close();
			} catch (IOException e)
			{
				e.printStackTrace();
			}
		}
	}

	final private MrgExpStats stats = new MrgExpStats();
	final private ArimaStats aStats = new ArimaStats();
	
	public Arima(String filePath) {
		super(filePath);
		this.stats.location = filePath;
		this.stats.className = this.getClass().getSimpleName();
		this.stats.write = write;
		this.aStats.location = filePath;
		this.aStats.className = this.getClass().getSimpleName();
		this.aStats.write = write;
	}

	/*
	 * *******************************************
	 * 
	 * 		First part of Arima Algorithm
	 * 
	 * *******************************************
	 */

	// list of unique 1-itemsets
//	public List<Integer> allItems = new ArrayList<Integer>();
//	public int[] allItems;
	// set of itemsets and their supports - note that this is INCOMPLETE - it
	// misses some non-generator frequent itemsets
//	public Map<Itemset, Integer> itemsetFreqsIncomplete = new HashMap<Itemset, Integer>();
	// set of frequent generators found during first part of ARIMA
//	public Set<Itemset> frequentGenerators = new HashSet<Itemset>();
	// set of rare generators found from first part of ARIMA
	public Map<BitSet, Integer> minRareGenerators = new HashMap<BitSet, Integer>();
	// set of zero generators - note that these are only those generated from
	// the first part of ARIMA, and may be incomplete
	public Map<BitSet, Integer> minZeroGeneratorsIncomplete = new HashMap<BitSet, Integer>();
//	private BufferedWriter bwZG = null;
//	private BufferedWriter bwMRG = null;
	
	public void findMinGenerators() {
		long t1 = System.nanoTime();

//		System.out.println("Running: " + this.getClass().getSimpleName());
//		System.out.println("minRareItemsetSup: " + this.getMinRareItemsetSupport() + " | minFreqItemsetSup: " + this.getMinFreqItemsetSupport());

		Vector<Integer> oneItemsetFreqs = this.countOneItemsets();
//		System.out.println("oneItemsetFreqs: " + oneItemsetFreqs);
		
		// stores current level of frequent generators
		Map<BitSet, Integer> currentFrequentGenerators = generatorAndSupportTest_1itemset(oneItemsetFreqs);

		int size = 1;
		while (!currentFrequentGenerators.isEmpty()) {
//			System.out.print(".");
//			System.out.println(((List<String>)currFgs.toArray()[0]).size());

			// testing
//			for (Itemset itemset : currentFrequentGenerators.keySet()) {
//				assert (itemsetFreqsIncomplete.get(itemset) >= minimumFrequentItemsetSupport);
//			}
			Map<BitSet, Integer> candidates = this.genCandidatesFirstPart(currentFrequentGenerators, size);
			Map<BitSet, Integer> ithLayerItemSetFreqs = this.countItemsetSupport(candidates.keySet(), size + 1);
//			System.out.println(candidates.size());
			currentFrequentGenerators = this.sortGenerators(candidates,	ithLayerItemSetFreqs);
			size++;
		}
//		System.out.println();
		
//		System.out.println("iteration itemset sizes: " + this.stats.numIterationItemsets);
//		System.out.println("number if items in all itemsets: " + this.stats.numItemsetItems);
//		System.out.println("result size: " + this.stats.numItemsets);
		
		long t2 = System.nanoTime();
		this.stats.runtime = (t2-t1)/1000000;
		this.stats.iterations = size;
		
	}
	
	private List<Integer> items = new ArrayList<Integer>();
	private Vector<BitSet> transactionRecord;
	private Vector<Integer> countOneItemsets() {
		this.transactionRecord = new Vector<BitSet>();
		this.transactionRecord.setSize(32);
		
		Vector<Integer> itemFreqs = new Vector<Integer>();
		itemFreqs.setSize(16);
		
		int transactionCount = 0;
		int maxItemName = 0;
		for (CsvReader reader = new CsvReader(this.filePath); reader.hasNext(); )
		{
			List<Integer> transaction = new ArrayList<Integer>(reader.read());
			if (this.transactionRecord.size() < transactionCount + 1) // resize vector
				this.transactionRecord.setSize((int) (this.transactionRecord.size() * 2));
			this.transactionRecord.set(transactionCount, new BitSet());
			for (int item : transaction) { // count item frequency
				this.transactionRecord.get(transactionCount).set(item);
				if (itemFreqs.size() <= item) // resize vector
					itemFreqs.setSize(itemFreqs.size() * 2);
				if (itemFreqs.get(item) == null) {
					maxItemName = Math.max(maxItemName, item + 1);
					itemFreqs.set(item, 1);
				} else {
					itemFreqs.set(item, itemFreqs.get(item)+1);
				}
			}
			transactionCount++;
		}
		this.transactionRecord.setSize(transactionCount);
		itemFreqs.setSize(maxItemName);
		
//		transactionRecord2.trimToSize();
//		itemFreqs.trimToSize();
		
		this.transactionCount = transactionCount;

		return itemFreqs;
	}
	
	long total = 0;
	long timeToDoNothing = 0;
	
	private Map<BitSet, Integer> genCandidatesFirstPart(Map<BitSet, Integer> currentFrequentGenerators, int size)
	{
		BitSet[] fGs = currentFrequentGenerators.keySet().toArray(new BitSet[currentFrequentGenerators.size()]);
		Map<BitSet, Integer> next = new HashMap<BitSet, Integer>(); 
		
		for (int i = 0; i < fGs.length; i++)
		{
			for (int j = i + 1; j < fGs.length; j++)
			{
				int index = allButLastSame(fGs[i], fGs[j]); 
				if (index != -1)
				{
					BitSet candidate = (BitSet) fGs[j].clone();
					candidate.set(index);
					
					if (!next.containsKey(candidate)) {
						int maxSubsetSupport = Integer.MIN_VALUE;
						boolean subsetExists = true;

						assert ((size + 1) == candidate.cardinality()) : (size + 1) + " does not equal " + candidate.cardinality();

						for (int item2 = candidate.nextSetBit(0); item2 >= 0; item2 = candidate.nextSetBit(item2 + 1))
						{
							BitSet subset = candidate;
							subset.set(item2, false);
							subsetExists = currentFrequentGenerators.containsKey(subset);
							if (!subsetExists) {
								subset.set(item2, true);
								break;
							} else {
								int subsetSupport = currentFrequentGenerators.get(subset);
								maxSubsetSupport = Math.max(maxSubsetSupport,subsetSupport);
								subset.set(item2, true);
							}
						}
						candidate.nextSetBit(0);

						if (subsetExists)
							next.put(candidate, maxSubsetSupport);

					}
				}
			}
		}
		
		return next;
	}
	
	// returns item that is different.  If more than 1 item different, or item in middle is different, returns -1.
	// e.g. {0,1,2,5}, {0,1,2,6} returns 5
	// e.g. {0,1,4,5}, {0,1,2,6} returns -1
	// e.g. {0,1,4,6}, {0,1,5,6} returns -1
	private int allButLastSame(BitSet a, BitSet b) {
		int oneDiff = -1;
		for (int i = a.nextSetBit(0); i >= 0; i = a.nextSetBit(i+1)) {
			if (oneDiff != -1)
				return -1;
			if (!b.get(i))
			{
				oneDiff = i;
			}
		}
		if (oneDiff == -1)
			throw new RuntimeException("both exactly the same");
		return oneDiff;
	}
	
	private class Node {
		int itemName;
//		Node parent;
		Map<Integer, Node> children;
		Map<Integer, Node> getChildren()
		{
			if (this.children == null)
				this.children = new HashMap<Integer, Node>();
			return this.children;
		}
		BitSet bitSet;
		int count;
		Node leafLink;
		boolean isLeaf()
		{
			return (this.children == null || this.children.isEmpty());
		}
		@Override
		public String toString()
		{
			return this.itemName + ": " + this.children;
		}
	}
	
	private Node constructTree(Set<BitSet> itemsets) {
		Node root = new Node();
		root.itemName = -1;
		Node prevLeaf = null;
		for (BitSet bitSet : itemsets)
		{
			Node node = root;
			for ( int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i+1))
			{
				if (node.getChildren().containsKey(i))
				{
					node = node.getChildren().get(i);
				} else
				{
					Node newNode = new Node();
					newNode.itemName = i;
//					newNode.parent = node;
					node.getChildren().put(i, newNode);
					node = newNode;
				}
			}
			node.bitSet = bitSet;
			if (prevLeaf == null)
			{
				prevLeaf = node;
				root.leafLink = node;
			}		
			else
			{
				prevLeaf.leafLink = node;
				prevLeaf = node;
			}	
		}
		return root;
	}
	
	// depth first traversal of tree.  Each item in the transaction (each set bit)
	// is used to go down a level in the tree.  If a leaf is reached, then the 
	// transaction includes the candidate (represented by the path from the root to
	// the leaf).
	private void traverseTree(Node node, BitSet transaction) {
		for (Node child : node.getChildren().values())
		{
			if (transaction.get(child.itemName))
			{
				if (child.isLeaf())
					child.count++;
				else
					traverseTree(child, transaction);
			}
		}
	}
	
	// size must equal the cardinality of the itemsets
	private Map<BitSet, Integer> countItemsetSupport(Set<BitSet> itemsets, int size) {
		Node root = constructTree(itemsets);
				
		for (BitSet transaction : this.transactionRecord) {
			traverseTree(root, transaction);
		}
		
		Map<BitSet, Integer> supportCounts = new HashMap<BitSet, Integer>(itemsets.size());
		for (Node leaf = root.leafLink; leaf != null; leaf = leaf.leafLink)
		{
			supportCounts.put(leaf.bitSet, leaf.count);
		}
		
		return supportCounts;
	}
	
	private boolean hasSubset_modified(BitSet transaction, BitSet subset) {
		for ( int item = subset.nextSetBit(0); item >= 0; item = subset.nextSetBit(item + 1)) {
			if (!transaction.get(item))
				return false;
		}
		return true;
	}
	
	long iterationItemsetCount;
	
	// put 1-itemsets into fgs or rgs or neither
	private Map<BitSet, Integer> generatorAndSupportTest_1itemset(Vector<Integer> oneItemsetFreqs) {
		this.iterationItemsetCount = 0;
		Map<BitSet, Integer> currentFrequentGenerators = new HashMap<BitSet, Integer>();
		for (int item = 0; item < oneItemsetFreqs.size(); item++) {
			BitSet itemset = new BitSet();
			itemset.set(item);
			int sup = 0;
			if (oneItemsetFreqs.get(item) != null)
			{
				sup = oneItemsetFreqs.get(item);
				this.items.add(item);
			}
			// check if support is less than empty set (i.e. is a generator)
			if (sup != getTransactionCount()) { 
			// System.out.println(entry.getKey() + " is a generator");
				if (sup < this.getMinRareItemsetSupport()) {
					this.minZeroGenerators.add(itemset);
				} // if less than support threshold, then this is a rare item generator
				else if (sup < this.getMinFreqItemsetSupport())
				{
					// testing
					// assertNotSubset(entry.getKey(), this.minRareGenerators);
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.minRareGenerators.put(itemset, sup);
				} else
				{ // otherwise is a frequent generator
	// this.frequentGenerators.add(entry.getKey());
					currentFrequentGenerators.put(itemset, sup);
				}
			}
		}
		this.itemCount = this.items.size();
		this.stats.numItemsets += this.iterationItemsetCount;
		this.stats.numIterationItemsets.add(this.iterationItemsetCount);
		return currentFrequentGenerators;
	}

	
	private Map<BitSet, Integer> sortGenerators(
							Map<BitSet, Integer> candidates,
							Map<BitSet, Integer> ithLayerItemSetFreqs) {

		this.iterationItemsetCount = 0;
		Map<BitSet, Integer> results = new HashMap<BitSet, Integer>();

		// testing
		assert (candidates.keySet().equals(ithLayerItemSetFreqs.keySet()));

		for (BitSet itemset : candidates.keySet()) {
			int sup = ithLayerItemSetFreqs.get(itemset);
			if (sup < candidates.get(itemset)) {	// test to determine if generator
				if (sup < this.getMinRareItemsetSupport()) { // "zero" generator
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.minZeroGeneratorsIncomplete.put(itemset, sup);
				} else if (sup < this.getMinFreqItemsetSupport()) { // rare generator
					this.iterationItemsetCount++;
					this.stats.numItemsetItems += itemset.cardinality();
					this.minRareGenerators.put(itemset, sup);
				} else { // frequent generator
					results.put(itemset, sup);
				}
			}
		}
		this.stats.numItemsets += this.iterationItemsetCount;
		this.stats.numIterationItemsets.add(this.iterationItemsetCount);

		return results;
	}
	
	// minimum zero generators
	public List<BitSet> minZeroGenerators = new ArrayList<BitSet>(); 
	// rare itemsets, excluding zero itemsets
//	public Set<BitSet> rareItemsets = new HashSet<BitSet>(); 
	private BufferedWriter bw = null;
	
	long aIterationItemsetCount = 0; // for 2nd part - arima
	
	private void generateRareItemsets() {
		if (this.minRareGenerators.isEmpty()) {
			return;
		}
		
		this.minZeroGenerators.addAll(this.minZeroGeneratorsIncomplete.keySet());

		// used to store all rare itemsets of the same size in the same bucket
		// so they can be processed together
		TreeMap<Integer, Set<BitSet>> layers = new TreeMap<Integer, Set<BitSet>>();
//		int smallestSize = Integer.MAX_VALUE; // stores the size of the smallest mRG, to begin at the lowest layer

		this.aStats.numItemsets += this.minRareGenerators.size();
		for (Entry<BitSet, Integer> entry : this.minRareGenerators.entrySet()) {
//			this.rareItemsets.add(entry.getKey());
			
			int currentMRGsize = entry.getKey().cardinality();
			
			// add all the mRGs into "layers" according to size
//			smallestSize = Math.min(smallestSize, currentMRGsize);
			if (!layers.containsKey(currentMRGsize)) {
				Set<BitSet> itemsetAsSet = new HashSet<BitSet>();
				itemsetAsSet.add(entry.getKey());
				layers.put(currentMRGsize, itemsetAsSet);
			} else {
				layers.get(currentMRGsize).add(entry.getKey());
			}

			// write all RGs from MRG_Exp to file
			this.aStats.numItemsetItems += currentMRGsize;
			this.writeToFile(this.bw, entry.getKey(), entry.getValue());
		}
		
		int lowestLayer = layers.firstKey();

		// holds all rare-itemsets of the same level
		Set<BitSet> currentLevel = layers.get(lowestLayer);

		// remove reference to this level so the same itemsets won't be processed again
		layers.remove(lowestLayer); 

		// stop only if there's no more rare-itemsets at a particular level
		while (!currentLevel.isEmpty()) {
			this.aIterationItemsetCount = 0;
			this.aStats.iterations++;
//			System.out.print(".");

			Set<BitSet> candidates = new HashSet<BitSet>();

			// candidate generation for all itemsets with the same size
			for (BitSet itemSet : currentLevel) {
				candidates.addAll(genCandidatesSecondPart(itemSet, this.items));
//				System.out.println("item: " + itemSet + " candidates: " + candidates);
			}

			// testing
//			for (Itemset candidate : candidates) {
//				assert (candidate.size() == smallestSize + 1);
//			}

//			 System.out.println("num candidates generated: " + candidates.size());

			/*
			 * swap the order of supportTest and zeroSubsetTest? will reduce the
			 * number of candidates for zeroSubsetTest
			 */

			// find candidates that have zero support
			
			Map<BitSet, Integer> itemsetFreqs = this.countItemsetSupport(candidates, lowestLayer + 1);

//			this.itemsetFreqsIncomplete.putAll(itemsetFreqs);

			Set<BitSet> zeroSupportCandidates = new HashSet<BitSet>();
			for (Entry<BitSet, Integer> candidate : itemsetFreqs.entrySet()) {
				if (candidate.getValue() < this.getMinRareItemsetSupport()) {
					candidates.remove(candidate.getKey());
					zeroSupportCandidates.add(candidate.getKey());
				} else {
					this.aIterationItemsetCount++;
					this.aStats.numItemsetItems += candidate.getKey().cardinality();
					this.writeToFile(this.bw, candidate.getKey(), candidate.getValue());
				}
			}

			// remove zeroItemsets that have one or more mZG subset
			findZeroGeneratorSubset(zeroSupportCandidates, this.minZeroGenerators, lowestLayer + 1);

			// add zero itemsets that have no zero generator subsets to list of zero generators
			this.minZeroGenerators.addAll(zeroSupportCandidates);

			// remaining candidates with non-zero support must be rare itemsets,
			// so add to results
//			this.rareItemsets.addAll(candidates);

			// remaining candidates will be used for generation next round,
			// but must add mZGs generated from first part of Arima for complete
			// set of candidates for the next level
			if (!candidates.isEmpty()) {
				if (layers.containsKey(lowestLayer + 1)) {
					layers.get(lowestLayer + 1).addAll(candidates);
				} else {
					layers.put(lowestLayer + 1, candidates);
				}
			}

			// find the size of the next smallest (set of) itemset
			// note that if there were no new rare itemsets generated,
			// smallestSize will
			// skip the level and find the next smallest.
			if (!layers.isEmpty()) {
				lowestLayer = layers.firstKey();
				currentLevel = layers.get(lowestLayer);
				layers.remove(lowestLayer);
			} else {
				// if there's nothing left in layers - i.e. no more candidates
				// to process then set currentLevel to empty. While-loop will break.
				currentLevel = Collections.emptySet();
			}

			this.aStats.numIterationItemsets.add(this.aIterationItemsetCount);
			this.aStats.numItemsets += this.aIterationItemsetCount;
		}
//		System.out.println();
	}

	// generate new candidates by performing cross-product between one itemset and each item
	private Set<BitSet> genCandidatesSecondPart(BitSet itemSet, List<Integer> items)
	{
		// stores set of candidates of size i+1
		Set<BitSet> next = new HashSet<BitSet>(); 
		for (int item : items)
		{
			if (!itemSet.get(item))
			{
				BitSet candidate = (BitSet) itemSet.clone();
				candidate.set(item);
				next.add(candidate);
			}
		}
		return next;
	}

	// modifies parameter "zeroSupportSets" and removes candidates with a mZG Subset
	private void findZeroGeneratorSubset(Set<BitSet> zeroSupportSets, List<BitSet> zgs, int size) {
//		System.out.println("zeroSets size before removal: " + zeroSupportSets.size());
//		long t1, t4, t5, ta, tb, totalA;

//		totalA = 0;
//		t1 = System.nanoTime();
		for (Iterator<BitSet> it = zeroSupportSets.iterator(); it.hasNext();) {
			BitSet zeroSupportSet = it.next();
			for (BitSet zg : zgs) {
				
//				ta = System.nanoTime();
				boolean isSubset = this.hasSubset_modified(zeroSupportSet, zg);
//				tb = System.nanoTime();
//				totalA += tb - ta;
				if (isSubset) {
					it.remove();
					break;
				}
			}
		}

//		t4 = System.nanoTime();

//		t5 = System.nanoTime();
//		System.out.println("\ttime: " + (t4 - t1 - totalA) / 1000000 + " | "
//				+ totalA / 1000000 + " | " + (t5 - t4) / 1000000 );
//		System.out.println("zeroSets size after removal: " +
//				zeroSupportSets.size() + "| zgs size: " + zgs.size() + "| removed: "
//				+ newWithZeroSubset.size());
	}
	
	private void writeToFile(BufferedWriter bw, BitSet itemset, int sup) {
		if (!write)
			return;
		try
		{
			bw.append(itemset.toString());
			bw.append(",");
			bw.append(Integer.toString(sup));
			bw.newLine();
		} catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	@Override
	public void setMinRareItemsetSupport(int minRareItemsetSupport)
	{
		super.setMinRareItemsetSupport(minRareItemsetSupport);
		this.stats.minRareItemsetSup = minRareItemsetSupport;
		this.aStats.minRareItemsetSup = minRareItemsetSupport;
	}

	@Override
	public void setMinFreqItemsetSupport(int minFreqItemsetSupport)
	{
		super.setMinFreqItemsetSupport(minFreqItemsetSupport);
		this.stats.minFreqItemsetSup = minFreqItemsetSupport;
		this.aStats.minFreqItemsetSup = minFreqItemsetSupport;
	}
}
